The present invention relates to a scheduling apparatus for an operating system which is capable of time-sharing processing a plurality of executable subjects, a method for the scheduling, and a recording medium in which an operating system capable of time-sharing processing a plurality of executable subjects is stored.
In a system which can run a number of executable subjects concurrently in time-sharing mode, the executable subjects are scheduled in order of priority levels attributed to the executable subjects respectively. More particularly, the executable subjects are queued in a wait queue depending on their priority levels so that the executable subject of the highest priority is executed first, and can thus be handled by a CPU (central processing unit) in the order of their priority levels. The executable subject may be a process, a task, a thread, or the like and in this specification, is illustrated as a thread. The system in which the executable subject is a thread is hence called a multi-thread system.
In such a multi-thread system, the order of importance of threads is defined by their priority levels which have been determined, e.g. when the threads were produced. The order is not limited to precedence for execution of a thread but, for example in time-slice scheduling, may be priority for a time slice of the processing time of a CPU imparted to a thread. In another case, the priority of a thread may be dynamically weighted with relation to the time consumption in the system and the processing time required for the thread.
With the use of an algorithm for scheduling in order of the priority, a drawback known as priority inversion may arise in the exclusive controlling of access to common resources. Such priority inversion is now explained referring to FIG. 1.
FIG. 1 is a diagram showing a typical attitude of the priority inversion. The priority inversion commonly occurs when a higher priority thread A enters a critical section CS1. It is noted that the critical section CS1 contains a resource commonly used by the thread A and a thread C.
It is assumed, as shown in FIG. 1, that when the thread C has entered the critical section CS1, the higher priority thread A is turned to its ready state. The execution of the thread C is thus interrupted and the execution of the thread A is started. However, because the thread C is present in the critical section CS1, the thread A has to wait until the thread C leaves from the critical section CS1. Accordingly, the thread A is in its wait state and, then, the execution of the thread C is started.
Under this condition, when a thread B of which the priority is between those of the thread A and the thread C is turned to its ready state before the thread C leaves from the critical section A, the priority inversion occurs. More specifically, even while the higher priority thread A is in its wait state, the execution of the thread B which is lower in the priority than the thread A is started. As the middle priority thread B has been turned to its ready state, the execution of the thread C is interrupted and the execution of the middle priority thread B is started. At the time, the thread A is still in its wait state. Since the relation between the thread A and the thread B is not defined except their priorities, the thread A will hardly presume how long its wait state lasts before its execution is resumed.
With the algorithm for scheduling in order of priority, such priority inversion may substantially occur causing a higher priority thread to wait for the completion of the execution of a lower priority thread. Also, when the priority inversion has once occurred, the duration of interruption of the execution of the higher priority thread will hardly be estimated. Failure of estimating the interruption time for a higher priority thread is critical for a real-time system (that is irresponsible if a process is not finished within a specific length of time).
For eliminating the drawback of priority inversion, priority inheritance schemes have been introduced (such as xe2x80x9cPriority Inheritance Protocols: An Approach to Real-time Synchronizationxe2x80x9d by Lui Sha, Ragunathan Rajkumar, and John P. Lehoczky, Technical Report CMU-CS-87-181, the Computer Science Department of Carnegie Mellon University, November 1987). The priority inheritance scheme is designed in which when a higher priority thread is turned to its wait state due to the presence of a lower priority thread, the lower priority thread inherits the priority level of the higher priority thread.
FIG. 2 illustrates a scenario, similar to that of FIG. 1, except for a priority inheritance scheme is employed. With the priority inheritance scheme, when the execution of a thread C is started with a thread A being in the wait state, the priority level of the thread C is changed to a level equal to the priority level of the thread A. As a result, interruption of the execution of the thread C by the execution of a thread (for example, the thread B) of which the priority level is lower than that of the thread A will be prevented before the thread C leaves from a critical section CS1.
The priority inheritance scheme allows the thread C to be scheduled at the priority level of the thread A before it leaves from the critical section CS1. Accordingly, the waiting time before the thread A is allowed to enter the critical section CS1 is bounded within a period required for the thread C occupying the critical section CS1. This permits an estimation of the interruption period during which the execution of the higher priority thread A is suspended.
To implement the above described priority inheritance scheme, the following procedure has to be performed. It is noted that this procedure is explained for a case that the execution of the higher priority thread A is interrupted until the lower priority thread C explicitly leaves from the critical section CS1.
First, as it has been judged that the thread A has to wait before the thread C leaves from the critical section CS1, i.e. the thread A is turned to its wait state, the thread A is dequeued from a wait queue. Then, the priority level of the thread C is temporarily changed to a level equal to the priority level of the thread A and the thread C is queued in the wait queue according to its priority level. The threads queued in the wait queue are performed by a CPU in order of the priority levels. When the thread C is called, its execution is started. In case that the processing time imparted to the thread C ends up during the execution, the thread C is queued again in the wait queue according to its changed priority level (equal to the priority level of the thread A).
When the wait state of the thread A is resolved (i.e. the thread C has left from the critical section CS1), the priority level of the thread C is turned back to its original lower level and the thread C is queued in the wait queue according to its original lower priority level. Simultaneously, the execution of the thread A becomes ready and queued back in the wait queue.
By following the foregoing procedure, the priority inheritance scheme shown in FIG. 2 is implemented where the interruption of the execution of the thread C by a thread (for example, the thread B) of which the priority level is lower than that of the thread A can be avoided before the thread C leaves out from the critical section CS1.
In a conventional scheduling system, the location in the wait queue of a thread to be queued is determined by its priority level at the time. Because the priority level is changed dynamically and frequently in the priority inheritance scheme, it is necessary to modify the wait queue at short intervals of time. Therefore, the use of the priority inheritance scheme requires modification or rescheduling of the wait queue to respond to the dynamic change of the priority level, hence resulting in increase of the overhead.
More particularly, the priority inheritance scheme is effective to eliminate the drawback of priority inversion, but demands for dynamically changing the priority level at high frequency thus increasing the overhead due to rescheduling and declining the overall performance of the system.
Also, in case that the priority is not just the order of execution of a thread but the ratio of use of the processing time of the CPU, i.e. the time-sharing scheduling is employed, changing the priority level of an interrupting thread (the thread C in the example) to a level equal to the priority level of a waiting thread (the thread A in the example) will discourage the optimum use of the processing time imparted to each thread.
More specifically, when the priority level of the thread C for example is set equal to the priority level of the thread A, the execution of the thread C is started with the priority level of the thread A and its processing time by the CPU is equal to the time imparted to the thread A but not the thread C. Accordingly, for implementing the optimum use of the overall processing time of the CPU, a sum of the time imparted to the waiting thread A and the time imparted to the interrupting thread C has to be calculated and imparted as the modified processing time to the thread C. In other words, it is essential for the time-sharing scheduling that the priority level corresponding to a sum of the processing time imparted to the thread A and the processing time imparted to the thread C is determined and assigned to the thread C.
However, such rescheduling by calculating the processing time imparted to each thread results in increase of the overhead during the execution. Accordingly, the conventional priority inheritance scheme will hardly ensure the optimum use of a processing time of the CPU imparted to each thread.
The present invention has been developed in view of the foregoing aspects and its object is to provide an apparatus and a method for scheduling in which the drawback of priority inversion can be resolved. Using the scheduling apparatus or method of the present invention, modification of the wait queue which may cause overhead can be minimized and a shared processing time of a CPU can be effectively used. Another object of the present invention is to provide a recording medium in which a data processing program of an operating system capable of time-sharing processing a plurality of executable subjects.
A scheduling apparatus according to the present invention for an operating system which is capable of time-sharing processing a plurality of executable subjects is provided comprising: a means for storing a time slot data which is assigned as the object to be scheduled to each of the executable subjects; a scheduler for imparting a processing time to the time slot data and conducting time-sharing scheduling; a means for executing the executable subject specified by the time slot data to which the processing time is imparted; a means for, when a first executable subject having a higher priority level has to wait for the completion of the execution of a second executable subject having a lower priority level, assigning the time slot data specifying the first executable subject to the second executable subject; and a means for, when the execution of the second executable subject is completed, assigning again the time slot data specifying the first executable subject to the first executable subject.
The scheduling apparatus of the present invention allows the time slot data to be designated separately of the executable subject and subjected to the scheduling, whereby when the executable subject of a higher priority level has to wait for the completion of the execution of the executable subject of a lower priority level, the priority inheritance can be carried out by implementing transfer of the time slot data which is low in the cost.
Also, another scheduling apparatus according to the present invention for an operating system which is capable of time-sharing processing a plurality of executable subjects is provided comprising: a means for storing a time slot data which is assigned as the object to be scheduled to each of the executable subjects; a scheduler for imparting a processing time to the time slot data and conducting time-sharing scheduling; a ring buffer composed of a plurality of wait queues, each permitting at least one time slot data to be allocated thereto; a means for executing the executable subject specified by the time slot data to which the processing time is imparted; a positioning means for determining one of the wait queues in the ring buffer, to which the time slot data is allocated, depending on a priority level of the executable subject specified by the time slot data; a means for, when allocation of the time slot data to the determined wait queue in the ring buffer is desired, allocating the time slot data to the last of the wait queue in the ring buffer; and a means for imparting the processing time to a time slot data located at the top of the wait queue in the ring buffer.
The another scheduling apparatus of the present invention allows the location in the ring buffer, to which the time slot data is allocated, to be determined depending on the priority level of the executable subject specified by the time slot data and commonly used by different time slot data of the same priority level. Consequently, the processing time of the CPU can effectively be shared by the executable subjects specified by their respective time slot data according to the priority level oft heir time slot.
Also, a scheduling method according to the present invention for use with an operating system which is capable of time-sharing processing a plurality of executable subjects is provided comprising the steps of: imparting a processing time to a time slot data which is assigned as the object to be scheduled to each of the executable subjects and conducting time-sharing scheduling; executing the executable subject specified by the time slot data to which the processing time is imparted; when a first executable subject having a higher priority level has to wait for the completion of the execution of a second executable subject having a lower priority level, assigning the time slot data specifying the first executable subject to the second executable subject; and when the execution of the second executable subject is completed, assigning again the time slot data specifying the first executable subject to the first executable subject.
The scheduling method of the present invention allows the time slot data to be designated separately of the executable subject and subjected to the scheduling, whereby when the executable subject of a higher priority level has to wait for the completion of the execution of the executable subject of a lower priority level, the priority inheritance can be carried out by implementing transfer of the time slot data which is low in the cost.
Another scheduling method according to the present invention for use with an operating system which is capable of time-sharing processing a plurality of executable subjects is provided comprising the steps of: imparting a processing time to a time slot data which is assigned as the object to be scheduled to each of the executable subjects and conducting time-sharing scheduling; executing the executable subject specified by the time slot data to which the processing time is imparted; determining one of wait queues provided in a ring buffer, to which the time slot data is allocated, depending on a priority level of the executable subject specified by the time slot data; when allocation of the time slot data to the determined wait queue in the ring buffer is desired, allocating the time slot data to the last of the wait queue in the ring buffer; and imparting the processing time to a time slot data located at the top of the wait queue in the ring buffer.
The another scheduling method of the present invention allows the location in the ring buffer, to which the time slot data is allocated, to be determined depending on the priority level of the executable subject specified by the time slot data and commonly used by different time slot data of the same priority level. Consequently, the processing time of the CPU can effectively be shared by the executable subjects specified by their respective time slot data according to the priority level of their time slot.
A recording medium according to the present invention in which a data processing program of an operating system which is capable of time-sharing processing a plurality of executable subjects is recorded is featured by the data processing program comprising the steps of: imparting a processing time to a time slot data which is assigned as the object to be scheduled to each of the executable subjects and conducting time-sharing scheduling; executing the executable subject specified by the time slot data to which the processing time is imparted; when a first executable subject having a higher priority level has to wait for the completion of the execution of a second executable subject having a lower priority level, assigning the time slot data specifying the first executable subject to the second executable subject; and when the execution of the second executable subject is completed, assigning again the time slot data specifying the first executable subject to the first executable subject.
Another recording medium according to the present invention in which a data processing program of an operating system which is capable of time-sharing processing a plurality of executable subjects is recordedis featured by the data processing program comprising the steps of: imparting a processing time to a time slot data which is assigned as the object to be scheduled to each of the executable subjects and conducting time-sharing scheduling; executing the executable subject specified by the time slot data to which the processing time is imparted; determining one of wait queues provided in a ring buffer, to which the time slot data is allocated, depending on a priority level of the executable subject specified by the time slot data; when allocation of the time slot data to the determined wait queue in the ring buffer is desired, allocating the time slot data to the last of the wait queue in the ring buffer; and imparting the processing time to a time slot data located at the top of the wait queue in the ring buffer.
According to the present invention, the time slot data assigned to a higher priority thread is used as a time slot data of a lower priority thread thus permitting the priority level of the higher priority thread to be transferred to the lower priority thread. As a result, the drawback of priority inversion will be resolved.
Also, according to the present invention, the priority inheritance is implemented by handing the time slot data assigned to the higher priority thread as the time slot data of the lower priority thread. This resolves frequent modification of the wait queue in the priority inheritance. Therefore, the priority inheritance can be conducted without proceeding frequent modification of the wait queue which may increase undesirable overhead.
Furthermore, according to the present invention, when the priority level has been transferred from the higher priority thread to the lower priority thread, both the processing time imparted to the higher priority thread and the processing time imparted to the lower priority thread can be utilized equally. In other words, a slice of the processing time imparted to each thread can be used at high efficiency.